The present invention relates generally to a data structure that may be used in network communications, and more particularly to an index for locating, or discovering, devices connected within a network.
Network discovery is a technique commonly used by gateway servers and network management servers to identify devices in a network with given characteristics, or traits, as a component of monitoring a network. Network devices generally refers to routers and switches, but may also include other networked devices, such as printers.
A Bloom filter is a memory-efficient, probabilistic data structure that supports approximate membership queries. When testing whether an object is a member of a set represented by a Bloom filter, a query may return “definitely not in set” or “may be in set,” with a small probability of false positives. A Bloom filter is typically implemented as a bit array into which a set of values, representing set elements, is hashed. In general, a Bloom filter may be considered when space is at a premium and the effect of false positives can be mitigated. Due to their efficiency, compact representation, and flexibility in allowing a trade-off between memory requirements and false positive probability, Bloom filters are popular in representing diverse sets of data. For example, they are used in databases, distributed systems, web caching, and other network applications, where systems need to share information about what resources they have.
A Bloom filter index organizes a collection of Bloom filters. Searching a Bloom filter index for a target Bloom filter typically involves comparing indexed Bloom filters with the target Bloom filter to find matches. Due to the pattern matching nature of the search, conventional indexes may be ineffective in locating indexed Bloom filters. A standard technique for locating Bloom filters in a collection of Bloom filters is to linearly search a list of Bloom filters. It would be advantageous to have an efficient, faster than linear, mechanism for indexing Bloom filters.